{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove All Ones With Row and Column Flips II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeOnes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #通过翻转行或列来去除所有的 1 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定&nbsp;<strong>下标从 0 开始&nbsp;</strong>的 <code>m x n</code> <strong>二进制&nbsp;</strong>矩阵 <code>grid</code>。</p>\n",
    "\n",
    "<p>在一次操作中，可以选择满足以下条件的任意 <code>i</code> 和 <code>j</code>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= j &lt; n</code></li>\n",
    "\t<li><code>grid[i][j] == 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>并将第 <code>i</code> 行和第 <code>j</code> 列中的&nbsp;<strong>所有&nbsp;</strong>单元格的值更改为零。</p>\n",
    "\n",
    "<p>返回<em>从&nbsp;</em><code>grid</code><em> 中删除所有 <code>1</code> 所需的最小操作数。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/13/image-20220213162716-1.png\" style=\"width: 709px; height: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,1,1],[1,1,1],[0,1,0]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "在第一个操作中，将第 1 行和第 1 列的所有单元格值更改为 0。\n",
    "在第二个操作中，将第 0 行和第 0 列的所有单元格值更改为 0。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/13/image-20220213162737-2.png\" style=\"width: 734px; height: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[0,1,0],[1,0,1],[0,1,0]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "在第一个操作中，将第 1 行和第 0 列的所有单元格值更改为 0。\n",
    "在第二个操作中，将第 2 行和第 1 列的所有单元格值更改为 0。\n",
    "注意，我们不能使用行 1 和列 1 执行操作，因为 grid[1][1]!= 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2022/02/13/image-20220213162752-3.png\" style=\"width: 156px; height: 150px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[0,0],[0,0]]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "没有 1 可以移除，所以返回0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 15</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 15</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-all-ones-with-row-and-column-flips-ii](https://leetcode.cn/problems/remove-all-ones-with-row-and-column-flips-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-all-ones-with-row-and-column-flips-ii](https://leetcode.cn/problems/remove-all-ones-with-row-and-column-flips-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1],[1,1,1],[0,1,0]]', '[[0,1,0],[1,0,1],[0,1,0]]', '[[0,0],[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        queue = collections.deque()\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        queue.append([grid,0])\n",
    "        while queue:\n",
    "            cur,step = queue.popleft()\n",
    "            flag = 1\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if cur[i][j]:\n",
    "                        flag = 0\n",
    "                        break\n",
    "                if not flag:\n",
    "                    break\n",
    "            if flag:\n",
    "                return step\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if cur[i][j]:\n",
    "                        temp = copy.deepcopy(cur)\n",
    "                        for k in range(m):\n",
    "                            if cur[i][k]:\n",
    "                                temp[i][k] = 0\n",
    "                        for k in range(n):\n",
    "                            if cur[k][j]:\n",
    "                                temp[k][j] = 0\n",
    "                        queue.append([temp,step + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        def check_zero(grid):\n",
    "            for i in grid:\n",
    "                for j in i:\n",
    "                    if j == 1:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def get_min(grid):\n",
    "            if check_zero(grid):\n",
    "                return 0\n",
    "            ret = math.inf\n",
    "            for k,v in enumerate(grid):\n",
    "                for k2, v2 in enumerate(v):\n",
    "                    if v2 == 1:\n",
    "                        newc = deepcopy(grid)\n",
    "                        for k1, vv1 in enumerate(newc):\n",
    "                            for kk2, vv2 in enumerate(vv1):\n",
    "                                if k1 == k or kk2 == k2:\n",
    "                                    newc[k1][kk2] = 0\n",
    "                        ans1 = 1 + get_min(newc)\n",
    "                        ret = min(ret, ans1)\n",
    "            return ret\n",
    "\n",
    "\n",
    "        return get_min(grid)\n",
    "\n",
    "a = Solution()\n",
    "print(a.removeOnes([[1,1,1],[1,1,1],[0,1,0]]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOnes(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if not state:\n",
    "                return 0\n",
    "            ans = inf\n",
    "            for i in range(m * n):\n",
    "                if (1 << i) & state:\n",
    "                    row, col = divmod(i, n)\n",
    "                    nxt_state = state\n",
    "                    for r in range(m):\n",
    "                        if (b:= 1 << (r * n + col)) & nxt_state:\n",
    "                            nxt_state ^= b\n",
    "                    for c in range(n):\n",
    "                        if (b:= 1 << (row * n + c)) & nxt_state:\n",
    "                            nxt_state ^= b\n",
    "                    ans = min(ans, dfs(nxt_state))\n",
    "            return ans + 1\n",
    "        \n",
    "        return dfs(sum(1 << (i * n + j) if grid[i][j] else 0 for i in range(m) for j in range(n)))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
